package org.leetcode.hard.leetcode239;

import java.util.*;

public class Solution {

    public int[] maxSlidingWindow5(int[] nums, int k) {

        List<Integer> res = new ArrayList<>();
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++) {
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.pollFirst();
            }

            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }

            deque.add(i);

            if (i >= k-1) {
                res.add(nums[deque.peek()]);
            }
        }

        int[] resArray = new int[res.size()];

        for (int i = 0; i < res.size(); i++) {
            resArray[i] = res.get(i);
        }

        return resArray;
    }

    /**
     * 复刻
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow3(int[] nums, int k) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();

        int n = nums.length;
        int[] res = new int[n - k + 1];

        int index = 0;

        for (int i = 0; i < n; i++) {

            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }

            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offer(i);

            if (i >= k - 1) {
                res[index++] = nums[deque.peek()];
            }
        }

        return res;
    }

    public int[] maxSlidingWindow2(int[] nums, int k) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();

        int n = nums.length;

        //n-k+1是窗口移动的次数
        int[] res = new int[n - k + 1];

        int idx = 0;

        for (int i = 0; i < n; i++) {

            // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
            // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }

            // 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
            // 如果将要push的数值大于入口元素的数值，那么就将队列入口处的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
            // 这样就保持了队列里的数值是单调从大到小的了。
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offer(i);


            if (i >= k - 1) {
                res[idx++] = nums[deque.peek()];
            }

        }

        return res;
    }

    /**
     * 超时
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {

        int arrLength = nums.length - (k - 1);

        int[] result = new int[arrLength];

        LinkedList<Integer> linkedList = new LinkedList<>();

        int left = 0;

        while (left + k - 1 <= nums.length - 1) {
            for (int i = left; i < left + k; i++) {

                if (linkedList.isEmpty()) {
                    linkedList.push(nums[i]);
                } else if (nums[i] > linkedList.peek()) {
                    linkedList.pop();
                    linkedList.push(nums[i]);
                }
            }
            result[left] = linkedList.pop();
            left++;
        }


        return result;
    }

    public static void main(String[] args) {
//        LRUCache solution = new LRUCache();
//
//       int [] nums = {1,3,-1,-3,5,3,6,7};
//        int[] ints = solution.maxSlidingWindow(nums, 3);
//
//        System.out.println(ints.length);

        ArrayDeque<Integer> deque = new ArrayDeque<>();

        deque.offer(1);
        deque.offer(2);

        Integer peek = deque.peek();
        Integer last = deque.peekLast();

        System.out.println(peek);

        System.out.println(last);
    }
}
